import java.util.Scanner;
import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 将单词列表转换为hash表，便于快速查找
        Set<String> wordHash = new HashSet<>(wordList);
        // 创建hash表 vis，用于记录是否遍历
        Set<String> vis = new HashSet<>();
        // 创建队列 q 用于执行宽度优先搜素
        Queue<String> q = new LinkedList<>();
        // 创建计数器
        int count = 0;

        // 执行宽度优先搜索 - 在入队时更新记录
        q.offer(beginWord);
        vis.add(beginWord);

        while(!q.isEmpty()) {
            count++;
            // (1) 将上次层序遍历的所有元素出队
            int curLen = q.size();
            for(int k = 0; k < curLen; k++) {
                // --(1) 出队
                String popElem = q.poll();
                // --(2) 枚举
                for(int i = 0; i < popElem.length(); i++) {
                    char[] tmp = popElem.toCharArray();
                    for(int j = 'a'; j <= 'z'; j++) {
                        tmp[i] = (char)j;
                        String s = new String(tmp);
                        if(wordHash.contains(s) && !vis.contains(s)) {
                            if(s.equals(endWord)) {
                                return count;
                            }
                            q.offer(s);
                            vis.add(s);
                        }
                    }
                }
            }
        }
        return 0;
    }
}

//class Main {
//    public static int find_x(int n) {
//        // x 表示阶层
//        int left = 1;
//        int right = n;
//        int answer = 0;
//        while(left <= right) {
//            int mid = left + (right - left) / 2;
//            if((1 + mid) * mid / 2 >= n) {
//                right = mid -1;
//                answer = mid;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return answer;
//    }
//    public static int func(int[] task, int n) {
//        // 1 特判
//        if(n == 0) {
//            return 0;
//        }
//        int x = find_x(n);
//        int y = n - x * (x-1) / 2;
//        return task[x-1] + x*y;
//    }
//
//    public static void main(String[] args) {
//
//        Scanner input = new Scanner(System.in);
//        // 1 接收数据
//        int q = input.nextInt();
//
//        // 2 准备任务前缀和数组 与 天数前缀和数组
//        // （1）任务前缀和数组
//        int n = (int)2e8;
//        int[] task = new int[n];
//        for(int i = 1; i < n; i++) {
//            task[i] = task[i-1] + i*i;
//        }
//        // 2 接收指令，准备主逻辑
//        for(int i = 0; i < q; i++) {
//            int l = input.nextInt();
//            int r = input.nextInt();
//            System.out.println(func(task, r) - func(task, l-1));
//        }
//    }
//}